{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Robot in a Grid LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming #backtracking #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划 #回溯 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: pathWithObstacles"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #迷路的机器人"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>设想有个机器人坐在一个网格的左上角，网格 r 行 c 列。机器人只能向下或向右移动，但不能走到一些被禁止的网格（有障碍物）。设计一种算法，寻找机器人从左上角移动到右下角的路径。</p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/10/22/robot_maze.png\" style=\"height: 183px; width: 400px;\"></p>\n",
    "\n",
    "<p>网格中的障碍物和空位置分别用 <code>1</code> 和 <code>0</code> 来表示。</p>\n",
    "\n",
    "<p>返回一条可行的路径，路径由经过的网格的行号和列号组成。左上角为 0 行 0 列。如果没有可行的路径，返回空数组。</p>\n",
    "\n",
    "<p><strong>示例&nbsp;1:</strong></p>\n",
    "\n",
    "<pre><strong>输入:\n",
    "</strong>[\n",
    "&nbsp; [<strong>0</strong>,<strong>0</strong>,<strong>0</strong>],\n",
    "&nbsp; [0,1,<strong>0</strong>],\n",
    "&nbsp; [0,0,<strong>0</strong>]\n",
    "]\n",
    "<strong>输出:</strong> [[0,0],[0,1],[0,2],[1,2],[2,2]]\n",
    "<strong>解释: \n",
    "</strong>输入中标粗的位置即为输出表示的路径，即\n",
    "0行0列（左上角） -&gt; 0行1列 -&gt; 0行2列 -&gt; 1行2列 -&gt; 2行2列（右下角）</pre>\n",
    "\n",
    "<p><strong>说明：</strong><em>r</em>&nbsp;和 <em>c </em>的值均不超过 100。</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [robot-in-a-grid-lcci](https://leetcode.cn/problems/robot-in-a-grid-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [robot-in-a-grid-lcci](https://leetcode.cn/problems/robot-in-a-grid-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "        dp = [[False] * len(obstacleGrid[0]) for _ in range(len(obstacleGrid))]\n",
    "        for row in range(len(obstacleGrid)):\n",
    "            for col in range(len(obstacleGrid[0])):\n",
    "                if row == 0 and col == 0 and obstacleGrid[0][0] == 0:\n",
    "                    dp[0][0] = True\n",
    "                    continue\n",
    "                if obstacleGrid[row][col] == 1:\n",
    "                    dp[row][col] = False\n",
    "                else:\n",
    "                    if row - 1 < 0:\n",
    "                        temp1 = False\n",
    "                    else:\n",
    "                        temp1 = dp[row-1][col]\n",
    "                    if col - 1 < 0:\n",
    "                        temp2 = False\n",
    "                    else:\n",
    "                        temp2 = dp[row][col-1]\n",
    "                    dp[row][col] = temp1 or temp2\n",
    "        if dp[-1][-1] == False:\n",
    "            return []\n",
    "        else:\n",
    "            ans = []\n",
    "            row, col = len(obstacleGrid)-1, len(obstacleGrid[0])-1\n",
    "            while row != 0 or col != 0:\n",
    "                ans.append([row, col])\n",
    "                if row - 1 >= 0 and dp[row-1][col]:\n",
    "                    row -= 1\n",
    "                else:\n",
    "                    col -= 1\n",
    "            ans.append([row, col])\n",
    "            return ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "        # DFS\n",
    "        # ans, r, c = [], len(obstacleGrid), len(obstacleGrid[0])\n",
    "        # def f(path):\n",
    "        #     if not ans:\n",
    "        #         i, j = path[-1]\n",
    "        #         if not obstacleGrid[i][j]:\n",
    "        #             obstacleGrid[i][j] = 1\n",
    "        #             if i < r - 1:\n",
    "        #                 f(path + [[i + 1, j]])\n",
    "        #             if j < c - 1:\n",
    "        #                 f(path + [[i, j + 1]])\n",
    "        #             if (i, j) == (r - 1, c - 1):\n",
    "        #                 ans.extend(path)\n",
    "        # f([[0, 0]])\n",
    "        # return ans\n",
    "\n",
    "        # DP\n",
    "        ## 逆序遍历矩阵，用状态码2和3分别表示该点可以向下还是像右，最后回溯路径。\n",
    "        ans, r, c = [], len(obstacleGrid), len(obstacleGrid[0])\n",
    "        if obstacleGrid[-1][-1] != 0:\n",
    "            return ans\n",
    "        obstacleGrid[-1][-1] = 2\n",
    "        for i in reversed(range(r)):\n",
    "            for j in reversed(range(c)):\n",
    "                if obstacleGrid[i][j] > 1:\n",
    "                    if i > 0 and not obstacleGrid[i - 1][j]:\n",
    "                        obstacleGrid[i - 1][j] = 2\n",
    "                    if j > 0 and not obstacleGrid[i][j - 1]:\n",
    "                        obstacleGrid[i][j - 1] = 3\n",
    "        if obstacleGrid[0][0] > 1:\n",
    "            i, j = 0, 0\n",
    "            while i < r and j < c:\n",
    "                ans.append([i, j])\n",
    "                if obstacleGrid[i][j] == 2:\n",
    "                    i += 1\n",
    "                else:\n",
    "                    j += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "        if obstacleGrid[-1][-1] == 1:\n",
    "            return []\n",
    "        mov = ((0,1),(1,0))\n",
    "        r, c = len(obstacleGrid) - 1, len(obstacleGrid[0]) - 1\n",
    "        res = []\n",
    "        def track(curNod: List[int]) -> bool:\n",
    "            to = False\n",
    "            x, y = curNod[0], curNod[1]\n",
    "            if obstacleGrid[x][y] == 1:\n",
    "                to = False\n",
    "            elif x == r and y == c:\n",
    "                to = True\n",
    "            else:\n",
    "                for m in mov :\n",
    "                    nextNod = [x + m[0], y + m[1]]\n",
    "                    if nextNod[0] > r or nextNod[1] > c : continue\n",
    "                    if track(nextNod) :\n",
    "                        to = True\n",
    "                        break\n",
    "            if to : res.append([x,y])\n",
    "            else: obstacleGrid[x][y] = 1\n",
    "            return to\n",
    "        if track([0,0]) : return res[::-1]\n",
    "        return []            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(obstacleGrid), len(obstacleGrid[0])\n",
    "        if obstacleGrid[0][0] or obstacleGrid[m - 1][n - 1]:\n",
    "            return []\n",
    "# 1. 定义状态矩阵，记录每一个状态最优解，自底向上求解最优解\n",
    "        dp = [[m + n + 1] * n for _ in range(m)] # 记录从起点到[i][j]的步数\n",
    "        pos = [[-1] * n for _ in range(m)] # 记录状态来源，比如，用1表示往下，2表示往右\n",
    "\n",
    "# 2. 边界初始化\n",
    "        pos[0][0] = 0\n",
    "        dp[0][0] = 0\n",
    "        for i in range(1, m):\n",
    "            if obstacleGrid[i][0] != 1:\n",
    "                dp[i][0] = i\n",
    "                pos[i][0] = 1\n",
    "            else:\n",
    "                break\n",
    "        for j in range(1, n):\n",
    "            if obstacleGrid[0][j] != 1:\n",
    "                dp[0][j] = j\n",
    "                pos[0][j] = 2\n",
    "            else:\n",
    "                break\n",
    "# 通过状态转移方程计算所有状态的最优解，同时，根据题目需要记录状态转移来源\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                if obstacleGrid[i][j] == 0 and (dp[i - 1][j] != m + n + 1 or dp[i][j - 1] != m + n + 1):\n",
    "                    if dp[i - 1][j] < dp[i][j - 1]:\n",
    "                        dp[i][j] = dp[i - 1][j] + 1\n",
    "                        pos[i][j] = 1 # 来自上边\n",
    "                    else:\n",
    "                        dp[i][j] = dp[i][j - 1] + 1\n",
    "                        pos[i][j] = 2 # 来自左边\n",
    "        if dp[m - 1][n - 1] == m + n + 1: # 判断是否存在路径\n",
    "            return []\n",
    "        else:\n",
    "            x, y = m - 1, n - 1\n",
    "            res = [[x, y]]\n",
    "            while pos[x][y] != 0: # 溯源，直到起点\n",
    "                t = pos[x][y]\n",
    "                if t == 1:\n",
    "                    x -= 1\n",
    "                else:\n",
    "                    y -= 1\n",
    "                res.append([x, y])\n",
    "            res.reverse() # 反转，形成一条从起点到终点的路径。\n",
    "\n",
    "            return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "        ans, r, c = [], len(obstacleGrid), len(obstacleGrid[0])\n",
    "        if obstacleGrid[-1][-1] != 0:\n",
    "            return ans\n",
    "        obstacleGrid[-1][-1] = 2\n",
    "        for i in range(r-1, -1, -1):\n",
    "            for j in range(c-1, -1, -1):\n",
    "                if obstacleGrid[i][j] > 1:\n",
    "                    if i > 0 and not obstacleGrid[i - 1][j]:\n",
    "                        obstacleGrid[i - 1][j] = 2\n",
    "                    if j > 0 and not obstacleGrid[i][j - 1]:\n",
    "                        obstacleGrid[i][j - 1] = 3\n",
    "        if obstacleGrid[0][0] > 1:\n",
    "            i, j = 0, 0\n",
    "            while i < r and j < c:\n",
    "                ans.append([i, j])\n",
    "                if obstacleGrid[i][j] == 2:\n",
    "                    i += 1\n",
    "                else:\n",
    "                    j += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "        self.m = 0\n",
    "        self.n = 0\n",
    "    def dfs(self, indexx, indexy, obstacleGrid):\n",
    "        # 边界和障碍物判断\n",
    "        if indexx >= self.m or indexy >= self.n:\n",
    "            return False\n",
    "        if obstacleGrid[indexx][indexy] == 1:\n",
    "            return False\n",
    "        self.res.append([indexx, indexy])\n",
    "        obstacleGrid[indexx][indexy] = 1\n",
    "        # 终止条件\n",
    "        if indexx == self.m-1 and indexy == self.n-1:\n",
    "            return True\n",
    "        \n",
    "        # 主循环\n",
    "        if self.dfs(indexx+1, indexy, obstacleGrid) or self.dfs(indexx, indexy+1, obstacleGrid):\n",
    "            return True\n",
    "        self.res.pop()\n",
    "        return False\n",
    "\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "        # 回溯\n",
    "        self.m = len(obstacleGrid)\n",
    "\n",
    "        self.n = len(obstacleGrid[0])\n",
    "\n",
    "        self.dfs(0, 0, obstacleGrid)\n",
    "\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "        if obstacleGrid[0][0] == 1 or obstacleGrid[-1][-1] == 1:\n",
    "            return []\n",
    "        m, n = len(obstacleGrid), len(obstacleGrid[0])\n",
    "        q = deque([])\n",
    "        q.append([[0, 0]])\n",
    "        postions = [[1, 0], [0, 1]]\n",
    "        while q:\n",
    "            path = q.pop()\n",
    "            x, y = path[-1][0], path[-1][1]\n",
    "            if x == m - 1 and y == n - 1:\n",
    "                return path\n",
    "            for x_a, y_a in postions:\n",
    "                if 0 <= x + x_a < m and 0 <= y + y_a < n and obstacleGrid[x+x_a][y + y_a] == 0:\n",
    "                    obstacleGrid[x + x_a][y + y_a] = 2\n",
    "                    q.append(path + [[x + x_a, y + y_a]])\n",
    "        return []\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "        self.m = 0\n",
    "        self.n = 0\n",
    "    def dfs(self, indexx, indexy, obstacleGrid):\n",
    "        # 边界和障碍物判断\n",
    "        if indexx >= self.m or indexy >= self.n:\n",
    "            return False\n",
    "        if obstacleGrid[indexx][indexy] == 1:\n",
    "            return False\n",
    "        self.res.append([indexx, indexy])\n",
    "        obstacleGrid[indexx][indexy] = 1  # 避免重复访问节点！！！！\n",
    "        # 终止条件\n",
    "        if indexx == self.m-1 and indexy == self.n-1:\n",
    "            return True\n",
    "        \n",
    "        # 主循环\n",
    "        if self.dfs(indexx+1, indexy, obstacleGrid) or self.dfs(indexx, indexy+1, obstacleGrid):\n",
    "            return True\n",
    "        self.res.pop()\n",
    "        return False\n",
    "\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "        # 回溯\n",
    "        self.m = len(obstacleGrid)\n",
    "\n",
    "        self.n = len(obstacleGrid[0])\n",
    "\n",
    "        self.dfs(0, 0, obstacleGrid)\n",
    "\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "        ans, r, c = [], len(obstacleGrid), len(obstacleGrid[0])\n",
    "        def f(path):\n",
    "            if not ans:\n",
    "                i, j = path[-1]\n",
    "                if not obstacleGrid[i][j]:\n",
    "                    obstacleGrid[i][j] = 1\n",
    "                    i < r - 1 and f(path + [[i + 1, j]])\n",
    "                    j < c - 1 and f(path + [[i, j + 1]])\n",
    "                    if (i, j) == (r - 1, c - 1):\n",
    "                        ans.extend(path)\n",
    "        f([[0, 0]])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "        ans, r, c = [], len(obstacleGrid) - 1, len(obstacleGrid[0]) - 1\n",
    "        def f(path):\n",
    "            if not ans:\n",
    "                i, j = path[-1]\n",
    "                if not obstacleGrid[i][j]:\n",
    "                    obstacleGrid[i][j] = 1\n",
    "                    j < c and f(path + [[i, j + 1]])\n",
    "                    i < r and f(path + [[i + 1, j]])\n",
    "                    i == r and j == c and ans.extend(path)\n",
    "        f([[0, 0]])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "        if not obstacleGrid:\n",
    "            return []\n",
    "        res = []\n",
    "        row, col = len(obstacleGrid), len(obstacleGrid[0])\n",
    "\n",
    "        # def dfs(i, j):\n",
    "        #     if i<0 or i>=row or j<0 or j>= col:\n",
    "        #         return False\n",
    "        #     if obstacleGrid[i][j]==1:\n",
    "        #         return False\n",
    "        #     obstacleGrid[i][j]==1\n",
    "        #     res.append([i,j])\n",
    "        #     if i == row-1 and j == col-1:\n",
    "        #         return True\n",
    "        #     for (dx, dy) in ((i+1, j), (i,j+1)):\n",
    "        #         if dfs(dx, dy):\n",
    "        #             return True\n",
    "\n",
    "        #     res.pop()\n",
    "        #     return False\n",
    "        # dfs(0,0)\n",
    "        # return res\n",
    "            \n",
    "        \n",
    "        def dfs(i, j):\n",
    "            if i<0 or i>row-1 or j <0 or j> col-1:\n",
    "                return False\n",
    "            if obstacleGrid[i][j] == 1:\n",
    "                return False\n",
    "\n",
    "            obstacleGrid[i][j] = 1\n",
    "            res.append([i,j])\n",
    "            if i == row-1 and j == col - 1:\n",
    "                return True\n",
    "            for (dx, dy) in ((i+1, j), (i,j+1)):\n",
    "                if dfs(dx, dy):\n",
    "                    return True\n",
    "            res.pop()\n",
    "            return False\n",
    "\n",
    "        dfs(0,0)\n",
    "        return res\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "        if not obstacleGrid: return []\n",
    "        r, c = len(obstacleGrid), len(obstacleGrid[0])\n",
    "        path = []\n",
    "\n",
    "        def dfs(x, y):\n",
    "            if x < 0 or x > r -1 or y < 0 or y > c - 1:\n",
    "                return False\n",
    "            if obstacleGrid[x][y] == 1:\n",
    "                return False\n",
    "            \n",
    "            obstacleGrid[x][y] = 1\n",
    "            path.append([x, y])\n",
    "            if x == r - 1 and y == c - 1:\n",
    "                return True\n",
    "            \n",
    "            for (dx, dy) in ((x + 1, y), (x, y + 1)):\n",
    "                if dfs(dx, dy):\n",
    "                    return True\n",
    "            \n",
    "            path.pop()\n",
    "            return False\n",
    "        \n",
    "        dfs(0, 0)\n",
    "        return path"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(obstacleGrid), len(obstacleGrid[0])\n",
    "        if obstacleGrid[0][0] or obstacleGrid[m - 1][n - 1]:\n",
    "            return []\n",
    "# 1. 定义状态矩阵，记录每一个状态最优解，自底向上求解最优解\n",
    "        dp = [[m + n + 1] * n for _ in range(m)] # 记录从起点到[i][j]的步数\n",
    "        pos = [[-1] * n for _ in range(m)] # 记录状态来源，比如，用1表示往下，2表示往右\n",
    "\n",
    "# 2. 边界初始化\n",
    "        pos[0][0] = 0\n",
    "        dp[0][0] = 0\n",
    "        for i in range(1, m):\n",
    "            if obstacleGrid[i][0] != 1:\n",
    "                dp[i][0] = i\n",
    "                pos[i][0] = 1\n",
    "            else:\n",
    "                break\n",
    "        for j in range(1, n):\n",
    "            if obstacleGrid[0][j] != 1:\n",
    "                dp[0][j] = j\n",
    "                pos[0][j] = 2\n",
    "            else:\n",
    "                break\n",
    "# 通过状态转移方程计算所有状态的最优解，同时，根据题目需要记录状态转移来源\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                if obstacleGrid[i][j] == 0 and (dp[i - 1][j] != m + n + 1 or dp[i][j - 1] != m + n + 1):\n",
    "                    if dp[i - 1][j] < dp[i][j - 1]:\n",
    "                        dp[i][j] = dp[i - 1][j] + 1\n",
    "                        pos[i][j] = 1 # 来自上边\n",
    "                    else:\n",
    "                        dp[i][j] = dp[i][j - 1] + 1\n",
    "                        pos[i][j] = 2 # 来自左边\n",
    "        if dp[m - 1][n - 1] == m + n + 1: # 判断是否存在路径\n",
    "            return []\n",
    "        else:\n",
    "            x, y = m - 1, n - 1\n",
    "            res = [[x, y]]\n",
    "            while pos[x][y] != 0: # 溯源，直到起点\n",
    "                t = pos[x][y]\n",
    "                if t == 1:\n",
    "                    x -= 1\n",
    "                else:\n",
    "                    y -= 1\n",
    "                res.append([x, y])\n",
    "            res.reverse() # 反转，形成一条从起点到终点的路径。\n",
    "\n",
    "            return res\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "        if not obstacleGrid: return []\n",
    "        row, col = len(obstacleGrid), len(obstacleGrid[0])\n",
    "        path = []\n",
    "\n",
    "        def dfs(x, y):\n",
    "            if x < 0 or x > row-1 or y < 0 or y > col-1:\n",
    "                return False\n",
    "            if obstacleGrid[x][y] == 1:\n",
    "                return False\n",
    "            \n",
    "            obstacleGrid[x][y] = 1\n",
    "            path.append([x, y])\n",
    "            if x == row - 1 and y == col - 1:\n",
    "                return True\n",
    "\n",
    "            for (dx, dy) in ((x+1, y), (x, y+1)):\n",
    "                if dfs(dx, dy):\n",
    "                    return True\n",
    "            path.pop()\n",
    "            return False\n",
    "        dfs(0, 0)\n",
    "        return path\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        if not grid:\n",
    "            return []\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        ans = []\n",
    "        def dfs(x, y):\n",
    "            if x<0 or y<0 or x>=n or y>=m:\n",
    "                return False\n",
    "            if grid[x][y] == 1:\n",
    "                return False\n",
    "            grid[x][y] = 1\n",
    "            ans.append([x,y])\n",
    "            if x==n-1 and y==m-1:\n",
    "                return True\n",
    "            for (nx, ny) in ((x+1,y),(x,y+1)):\n",
    "                if dfs(nx,ny):\n",
    "                    return True\n",
    "            ans.pop()\n",
    "            return False\n",
    "        dfs(0,0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "        if not obstacleGrid: return []\n",
    "        row, col = len(obstacleGrid), len(obstacleGrid[0])\n",
    "        path = []\n",
    "\n",
    "        def dfs(x, y):\n",
    "            if x < 0 or x > row-1 or y < 0 or y > col-1:\n",
    "                return False\n",
    "            if obstacleGrid[x][y] == 1:\n",
    "                return False\n",
    "            \n",
    "            obstacleGrid[x][y] = 1\n",
    "            path.append([x, y])\n",
    "            if x == row - 1 and y == col - 1:\n",
    "                return True\n",
    "\n",
    "            for (dx, dy) in ((x+1, y), (x, y+1)):\n",
    "                if dfs(dx, dy):\n",
    "                    return True\n",
    "            path.pop()\n",
    "            return False\n",
    "        dfs(0, 0)\n",
    "        return path"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "        rows = len(obstacleGrid)\n",
    "        cols = len(obstacleGrid[0])\n",
    "\n",
    "        dp = [[0] * cols for _ in range(rows)]\n",
    "        row = 0\n",
    "        ob_flag = 0\n",
    "        for col in range(cols):\n",
    "            if obstacleGrid[row][col] == 1:\n",
    "                ob_flag = 1\n",
    "            if not ob_flag:\n",
    "                dp[row][col] = 1\n",
    "            else:\n",
    "                dp[row][col] = 0\n",
    "        \n",
    "        col = 0\n",
    "        ob_flag = 0\n",
    "        for row in range(rows):\n",
    "            if obstacleGrid[row][col] == 1:\n",
    "                ob_flag = 1\n",
    "            if not ob_flag:\n",
    "                dp[row][col] = 1\n",
    "            else:\n",
    "                dp[row][col] = 0\n",
    "\n",
    "        for row in range(1, rows):\n",
    "            for col in range(1, cols):\n",
    "                if obstacleGrid[row][col] == 1:\n",
    "                    continue \n",
    "                else:\n",
    "                    dp[row][col] = dp[row-1][col] + dp[row][col-1]\n",
    "        \n",
    "        if dp[-1][-1] == 0:\n",
    "            return []\n",
    "        else:\n",
    "            row = rows-1\n",
    "            col = cols-1\n",
    "            res = [[row, col]]\n",
    "                \n",
    "            while row > 0 or col > 0:\n",
    "                if row > 0 and dp[row-1][col] > 0:\n",
    "                    row -= 1\n",
    "                    res.append([row, col])\n",
    "                elif col > 0 and dp[row][col-1] > 0:\n",
    "                    col -= 1\n",
    "                    res.append([row, col])\n",
    "            \n",
    "            if [0, 0] not in res:\n",
    "                res.append([0, 0])\n",
    "\n",
    "            return res[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, g: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(g), len(g[0])\n",
    "        ans = []\n",
    "        v = [[False]*(n) for _ in range(m)]\n",
    "        def dfs(x, y, path):\n",
    "            nonlocal g, m, n, ans\n",
    "            if g[x][y] == 1:\n",
    "                return\n",
    "            v[x][y] = True\n",
    "            # 走右边\n",
    "            if x == m-1 and y == n-1:\n",
    "                ans = deepcopy(path)\n",
    "                return\n",
    "            if y + 1 < n and not v[x][y+1]:\n",
    "                path.append([x, y+1])\n",
    "                dfs(x, y+1, path)\n",
    "                path.pop()\n",
    "            # 走下边\n",
    "            if x + 1 < m and not v[x+1][y]:\n",
    "                path.append([x+1, y])\n",
    "                dfs(x+1, y, path)\n",
    "                path.pop()\n",
    "            return\n",
    "        \n",
    "        dfs(0, 0, [[0, 0]])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "        rows = len(obstacleGrid)\n",
    "        cols = len(obstacleGrid[0])\n",
    "\n",
    "        dp = [[0] * cols for _ in range(rows)]\n",
    "        row = 0\n",
    "        ob_flag = 0\n",
    "        for col in range(cols):\n",
    "            if obstacleGrid[row][col] == 1:\n",
    "                ob_flag = 1\n",
    "            if not ob_flag:\n",
    "                dp[row][col] = 1\n",
    "            else:\n",
    "                dp[row][col] = 0\n",
    "        \n",
    "        col = 0\n",
    "        ob_flag = 0\n",
    "        for row in range(rows):\n",
    "            if obstacleGrid[row][col] == 1:\n",
    "                ob_flag = 1\n",
    "            if not ob_flag:\n",
    "                dp[row][col] = 1\n",
    "            else:\n",
    "                dp[row][col] = 0\n",
    "\n",
    "        for row in range(1, rows):\n",
    "            for col in range(1, cols):\n",
    "                if obstacleGrid[row][col] == 1:\n",
    "                    continue \n",
    "                else:\n",
    "                    dp[row][col] = dp[row-1][col] + dp[row][col-1]\n",
    "        \n",
    "        if dp[-1][-1] == 0:\n",
    "            return []\n",
    "        else:\n",
    "            row = rows-1\n",
    "            col = cols-1\n",
    "            res = [[row, col]]\n",
    "                \n",
    "            while row > 0 or col > 0:\n",
    "                if row > 0 and dp[row-1][col] > 0:\n",
    "                    row -= 1\n",
    "                    res.append([row, col])\n",
    "                elif col > 0 and dp[row][col-1] > 0:\n",
    "                    col -= 1\n",
    "                    res.append([row, col])\n",
    "            \n",
    "            if [0, 0] not in res:\n",
    "                res.append([0, 0])\n",
    "\n",
    "            return res[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "        if obstacleGrid[0][0] == 1 or obstacleGrid[-1][-1] == 1:\n",
    "            return []\n",
    "        \n",
    "        q = deque([])\n",
    "        path = [[0, 0]]\n",
    "        q.append(path)\n",
    "\n",
    "        m, n = len(obstacleGrid), len(obstacleGrid[0])\n",
    "\n",
    "        while q:\n",
    "            path = q.popleft()\n",
    "            x, y = path[-1][0], path[-1][1]\n",
    "            if x == m - 1 and y == n - 1:\n",
    "                return path\n",
    "            if x + 1 < m and y < n and obstacleGrid[x + 1][y] == 0:\n",
    "                obstacleGrid[x + 1][y] = 2\n",
    "                q.append(path + [[x + 1, y]])\n",
    "            if x<m and y + 1 < n and obstacleGrid[x][y + 1] == 0:\n",
    "                obstacleGrid[x][y + 1] = 2\n",
    "                q.append(path + [[x, y + 1]])\n",
    "        return []\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "        rows = len(obstacleGrid)\n",
    "        cols = len(obstacleGrid[0])\n",
    "\n",
    "        dp = [[0] * cols for _ in range(rows)]\n",
    "        row = 0\n",
    "        ob_flag = 0\n",
    "        for col in range(cols):\n",
    "            if obstacleGrid[row][col] == 1:\n",
    "                ob_flag = 1\n",
    "            if not ob_flag:\n",
    "                dp[row][col] = 1\n",
    "            else:\n",
    "                dp[row][col] = 0\n",
    "        \n",
    "        col = 0\n",
    "        ob_flag = 0\n",
    "        for row in range(rows):\n",
    "            if obstacleGrid[row][col] == 1:\n",
    "                ob_flag = 1\n",
    "            if not ob_flag:\n",
    "                dp[row][col] = 1\n",
    "            else:\n",
    "                dp[row][col] = 0\n",
    "\n",
    "        for row in range(1, rows):\n",
    "            for col in range(1, cols):\n",
    "                if obstacleGrid[row][col] == 1:\n",
    "                    continue \n",
    "                else:\n",
    "                    dp[row][col] = dp[row-1][col] + dp[row][col-1]\n",
    "        \n",
    "        if dp[-1][-1] == 0:\n",
    "            return []\n",
    "        else:\n",
    "            row = rows-1\n",
    "            col = cols-1\n",
    "            res = [[row, col]]\n",
    "                \n",
    "            while row > 0 or col > 0:\n",
    "                if row > 0 and dp[row-1][col] > 0:\n",
    "                    row -= 1\n",
    "                    res.append([row, col])\n",
    "                elif col > 0 and dp[row][col-1] > 0:\n",
    "                    col -= 1\n",
    "                    res.append([row, col])\n",
    "            \n",
    "            if [0, 0] not in res:\n",
    "                res.append([0, 0])\n",
    "\n",
    "            return res[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        ans=[]\n",
    "        \n",
    "        rows=len(grid)\n",
    "        cols=len(grid[0])\n",
    "\n",
    "        \n",
    "        path=[]\n",
    "        visited=[[False]*cols for _ in range(rows)]  ##无后效性，所以 visited数组不用回溯\n",
    "        def dfs(r,c): \n",
    "            \n",
    "            nonlocal ans\n",
    "            \n",
    "            path.append([r,c])          \n",
    "            if r>=rows or c >=cols or  grid[r][c]==1 or visited[r][c]:\n",
    "                return \n",
    "            \n",
    "            if r== rows-1 and c==cols -1:\n",
    "                # print(path)\n",
    "                ans=path.copy()\n",
    "                return\n",
    "            visited[r][c]=True\n",
    "            dfs(r+1,c)\n",
    "            path.pop()\n",
    "            # visited[r][c]=False  ##不需要回溯，无后效性\n",
    "\n",
    "            visited[r][c]=True\n",
    "            dfs(r,c+1) \n",
    "            path.pop()\n",
    "            # visited[r][c]=False\n",
    "                \n",
    "        dfs(0,0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        m = len(obstacleGrid)\n",
    "        n = len(obstacleGrid[0])\n",
    "\n",
    "        # 此题关键，设置已访问数组，进行剪枝，否则会超时\n",
    "        visited = [[False for _ in range(n)] for _ in range(m)]\n",
    "\n",
    "        self.res = []\n",
    "\n",
    "        # 针对奇葩用例，来就是障碍，走不动\n",
    "        if obstacleGrid[0][0] == 1:\n",
    "            return self.res\n",
    "\n",
    "        def dfs(i, j, path):\n",
    "            if i == m-1 and j == n-1: # 走到终点了\n",
    "                self.res = path.copy()\n",
    "                return\n",
    "            \n",
    "            for x, y in [(0, 1), (1, 0)]: # 往右或者下走一步\n",
    "                next_i = i + x\n",
    "                next_j = j + y\n",
    "\n",
    "                # 越界、有障碍、已走过，都停止进一步dfs\n",
    "                if next_i >= m or next_j >= n or obstacleGrid[next_i][next_j] == 1 or visited[next_i][next_j]:\n",
    "                    continue\n",
    "\n",
    "                path.append([next_i, next_j])\n",
    "                visited[next_i][next_j] = True\n",
    "\n",
    "                dfs(next_i, next_j, path)\n",
    "\n",
    "                path.pop()\n",
    "\n",
    "        visited[0][0] = True\n",
    "        dfs(0, 0, [[0, 0]])\n",
    "\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, g: List[List[int]]) -> List[List[int]]:\n",
    "        n, m = len(g), len(g[0])\n",
    "        st = [[False] * m for _ in range(n)]\n",
    "        idx = [[[-1, -1] for _ in range(m)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if g[i][j] == 1: continue\n",
    "                if i == 0 and j == 0: \n",
    "                    st[i][j] = True\n",
    "                    continue\n",
    "                if i == 0: \n",
    "                    st[i][j] = st[i][j - 1]\n",
    "                    if st[i][j]: idx[i][j][0] = j - 1\n",
    "                elif j == 0:\n",
    "                    st[i][j] = st[i - 1][j]\n",
    "                    if st[i][j]: idx[i][j][1] = i - 1\n",
    "                else:\n",
    "                    if st[i - 1][j]:\n",
    "                        st[i][j] = True\n",
    "                        idx[i][j][1] = i - 1\n",
    "                    if st[i][j - 1]:\n",
    "                        st[i][j] = True\n",
    "                        idx[i][j][0] = j - 1\n",
    "        if not st[n - 1][m - 1]: return []\n",
    "        res = []\n",
    "        i, j = n - 1, m - 1\n",
    "        while True:\n",
    "            res.append([i, j])\n",
    "            a, b = -1, -1\n",
    "            if idx[i][j][0] != -1: i, j = i, j - 1\n",
    "            elif idx[i][j][1] != -1: i, j = i - 1, j\n",
    "            else: break\n",
    "        return res[::-1]\n",
    "                    \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, g: List[List[int]]) -> List[List[int]]:\n",
    "        n, m = len(g), len(g[0])\n",
    "        st = [[False] * m for _ in range(n)]\n",
    "        idx = [[[-1, -1] for _ in range(m)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if g[i][j] == 1: continue\n",
    "                if i == 0 and j == 0: \n",
    "                    st[i][j] = True\n",
    "                    continue\n",
    "                if i == 0: \n",
    "                    st[i][j] = st[i][j - 1]\n",
    "                    if st[i][j]: idx[i][j][0] = j - 1\n",
    "                elif j == 0:\n",
    "                    st[i][j] = st[i - 1][j]\n",
    "                    if st[i][j]: idx[i][j][1] = i - 1\n",
    "                else:\n",
    "                    if st[i - 1][j]:\n",
    "                        st[i][j] = True\n",
    "                        idx[i][j][1] = i - 1\n",
    "                    if st[i][j - 1]:\n",
    "                        st[i][j] = True\n",
    "                        idx[i][j][0] = j - 1\n",
    "        if not st[n - 1][m - 1]: return []\n",
    "        res = []\n",
    "        i, j = n - 1, m - 1\n",
    "        while True:\n",
    "            res.append([i, j])\n",
    "            if idx[i][j][0] != -1: i, j = i, j - 1\n",
    "            elif idx[i][j][1] != -1: i, j = i - 1, j\n",
    "            else: break\n",
    "        return res[::-1]\n",
    "                    \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(obstacleGrid)\n",
    "        n = len(obstacleGrid[0])\n",
    "        if obstacleGrid[0][0]==1:\n",
    "                return []\n",
    "       \n",
    "        dp = [[None] * (n+1) for _ in range(m+1)]\n",
    "        dp[1][1] = (-1, -1)\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                if dp[i-1][j] is not None and i>=1 and j>=1 and obstacleGrid[i-1][j-1]==0:\n",
    "                    dp[i][j] = [i-2, j-1]\n",
    "                elif dp[i][j-1] is not None and i>=1 and j>=1 and obstacleGrid[i-1][j-1]==0:\n",
    "                    dp[i][j] = [i-1, j-2]\n",
    "        res = []\n",
    "        if dp[-1][-1] is None: return res\n",
    "        p = dp[-1][-1]\n",
    "        while p[0] !=-1 or p[1]!=-1:\n",
    "            res.insert(0, p)\n",
    "            p = dp[p[0]+1][p[1]+1]\n",
    "        res.append([m-1, n-1])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(obstacleGrid), len(obstacleGrid[0])\n",
    "\n",
    "        def bt(x, y):\n",
    "            if x == m - 1 and y == n - 1:\n",
    "                return path\n",
    "            for nx, ny in ((x, y + 1), (x + 1, y)):\n",
    "                if nx < m and ny < n and not obstacleGrid[nx][ny] and nx * n + ny not in vis:\n",
    "                    path.append([nx, ny])\n",
    "                    if l := bt(nx, ny): return l\n",
    "                    path.pop()\n",
    "                    vis.add(nx * n + ny)\n",
    "            return []\n",
    "\n",
    "        vis = set([0])\n",
    "        path = [[0, 0]]\n",
    "        return [] if obstacleGrid[0][0] else bt(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(obstacleGrid), len(obstacleGrid[0])\n",
    "\n",
    "        def bt(x, y):\n",
    "            if x == m - 1 and y == n - 1:\n",
    "                return path\n",
    "            for nx, ny in ((x, y + 1), (x + 1, y)):\n",
    "                if nx < m and ny < n and not obstacleGrid[nx][ny] and nx * n + ny not in vis:\n",
    "                    path.append([nx, ny])\n",
    "                    if l := bt(nx, ny): return l\n",
    "                    path.pop()\n",
    "                    vis.add(nx * n + ny)\n",
    "            return []\n",
    "\n",
    "        vis = set([0])\n",
    "        path = [[0, 0]]\n",
    "        return [] if obstacleGrid[0][0] else bt(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(obstacleGrid), len(obstacleGrid[0])\n",
    "        if obstacleGrid[0][0] or obstacleGrid[m - 1][n - 1]:\n",
    "            return []\n",
    "# 1. 定义状态矩阵，记录每一个状态最优解，自底向上求解最优解\n",
    "        dp = [[m + n + 1] * n for _ in range(m)] # 记录从起点到[i][j]的步数\n",
    "        pos = [[-1] * n for _ in range(m)] # 记录状态来源，比如，用1表示往下，2表示往右\n",
    "\n",
    "# 2. 边界初始化\n",
    "        pos[0][0] = 0\n",
    "        dp[0][0] = 0\n",
    "        for i in range(1, m):\n",
    "            if obstacleGrid[i][0] != 1:\n",
    "                dp[i][0] = i\n",
    "                pos[i][0] = 1\n",
    "            else:\n",
    "                break\n",
    "        for j in range(1, n):\n",
    "            if obstacleGrid[0][j] != 1:\n",
    "                dp[0][j] = j\n",
    "                pos[0][j] = 2\n",
    "            else:\n",
    "                break\n",
    "# 通过状态转移方程计算所有状态的最优解，同时，根据题目需要记录状态转移来源\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                if obstacleGrid[i][j] == 0 and (dp[i - 1][j] != m + n + 1 or dp[i][j - 1] != m + n + 1):\n",
    "                    if dp[i - 1][j] < dp[i][j - 1]:\n",
    "                        dp[i][j] = dp[i - 1][j] + 1\n",
    "                        pos[i][j] = 1 # 来自上边\n",
    "                    else:\n",
    "                        dp[i][j] = dp[i][j - 1] + 1\n",
    "                        pos[i][j] = 2 # 来自左边\n",
    "        if dp[m - 1][n - 1] == m + n + 1: # 判断是否存在路径\n",
    "            return []\n",
    "        else:\n",
    "            x, y = m - 1, n - 1\n",
    "            res = [[x, y]]\n",
    "            while pos[x][y] != 0: # 溯源，直到起点\n",
    "                t = pos[x][y]\n",
    "                if t == 1:\n",
    "                    x -= 1\n",
    "                else:\n",
    "                    y -= 1\n",
    "                res.append([x, y])\n",
    "            res.reverse() # 反转，形成一条从起点到终点的路径。\n",
    "\n",
    "            return res\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "        if not obstacleGrid: return []\n",
    "        row, col = len(obstacleGrid), len(obstacleGrid[0])\n",
    "        path = []\n",
    "\n",
    "        def dfs(x, y):\n",
    "            if x < 0 or x > row-1 or y < 0 or y > col-1:\n",
    "                return False\n",
    "            if obstacleGrid[x][y] == 1:\n",
    "                return False\n",
    "            \n",
    "            obstacleGrid[x][y] = 1\n",
    "            path.append([x, y])\n",
    "            if x == row - 1 and y == col - 1:\n",
    "                return True\n",
    "\n",
    "            for (dx, dy) in ((x+1, y), (x, y+1)):\n",
    "                if dfs(dx, dy):\n",
    "                    return True\n",
    "            path.pop()\n",
    "            return False\n",
    "        dfs(0, 0)\n",
    "        return path\n",
    "\n",
    "class Solution:\n",
    "    def print_path(self, path):\n",
    "        curNode = path[-1]\n",
    "        realPath = []   \n",
    "        while curNode[2] != -1:\n",
    "            realPath.append(curNode[0:2])  #坐标\n",
    "            curNode = path[curNode[2]]   # 下一节点\n",
    "    # 这里是起点最后才添加进去\n",
    "        realPath.append(curNode[0:2])\n",
    "        realPath.reverse()\n",
    "        return realPath\n",
    "\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "        if not obstacleGrid: return []\n",
    "        row, col = len(obstacleGrid), len(obstacleGrid[0])\n",
    "            \n",
    "        if obstacleGrid[0][0] == 1:\n",
    "            return []\n",
    "\n",
    "        path = []   # 保存路径\n",
    "        queue = []  # 保存进行bfs操作的临时状态\n",
    "        queue.append((0, 0, -1))  # 0, 0表示起点坐标， -1表示入口节点\n",
    "        while len(queue) > 0:\n",
    "            curNode = queue.pop()\n",
    "            path.append(curNode)\n",
    "            x, y = curNode[0], curNode[1]\n",
    "\n",
    "            if x == row-1 and y == col-1:\n",
    "                return self.print_path(path)\n",
    "            \n",
    "            for (dx, dy) in ((x+1, y), (x, y+1)):\n",
    "                if  0 <= dx < row and 0 <= dy < col and obstacleGrid[dx][dy] == 0:\n",
    "                    queue.append((dx, dy, len(path)-1))    # len(path)-1)表示每个分叉地方的节点\n",
    "                    obstacleGrid[dx][dy] = 1  # 标记走过\n",
    "        else:\n",
    "            return [] \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "        path = []\n",
    "        visited = set()\n",
    "        def dfs(i,j):\n",
    "            if (i,j) in visited or (not 0<=i<len(obstacleGrid)) or (not 0<=j<len(obstacleGrid[0])) or obstacleGrid[i][j]==1:\n",
    "                return False\n",
    "            visited.add((i,j))\n",
    "            path.append([i,j])\n",
    "            if (i,j)==(len(obstacleGrid)-1,len(obstacleGrid[0])-1) or dfs(i+1,j) or dfs(i,j+1):\n",
    "                return True\n",
    "            path.pop()\n",
    "        dfs(0,0)\n",
    "        return path\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "        if obstacleGrid[0][0]==1 or obstacleGrid[-1][-1]==1:\n",
    "            return []\n",
    "        path=[]\n",
    "        m,n=len(obstacleGrid),len(obstacleGrid[0])\n",
    "        @cache\n",
    "        def dfs(x,y):\n",
    "            if x<0 or x>m-1 or y<0 or y>n-1:\n",
    "                return False\n",
    "            if obstacleGrid[x][y]==1:\n",
    "                return False\n",
    "            obstacleGrid[x][y]==1\n",
    "            if x==m-1 and y==n-1:\n",
    "                path.append([x,y])\n",
    "                return True\n",
    "            path.append([x,y])\n",
    "            if dfs(x+1,y) or dfs(x,y+1):\n",
    "                    return True\n",
    "            path.pop()\n",
    "            obstacleGrid[x][y]=0\n",
    "            return False\n",
    "        dfs(0,0)\n",
    "        return path\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "        if obstacleGrid[0][0]==1 or obstacleGrid[-1][-1]==1:\n",
    "            return []\n",
    "\n",
    "        ans_all = list()\n",
    "        visited_list = set()\n",
    "        def search(i, j, ans):\n",
    "            if i == len(obstacleGrid)-1 and j == len(obstacleGrid[0])-1:\n",
    "                ans_all.append(ans)\n",
    "                return\n",
    "            if len(ans_all) > 0:\n",
    "                return\n",
    "            \n",
    "            visited_list.add((i, j))\n",
    "            if j+1 < len(obstacleGrid[0]) and obstacleGrid[i][j+1] != 1 and (i,j+1) not in visited_list:\n",
    "                search(i, j+1, ans+[[i, j+1]])\n",
    "            if i+1 < len(obstacleGrid) and obstacleGrid[i+1][j] != 1 and (i+1, j) not in visited_list:\n",
    "                search(i+1, j, ans+[[i+1, j]])\n",
    "\n",
    "        search(0, 0, [[0,0]])\n",
    "        \n",
    "        return ans_all[0] if len(ans_all) > 0 else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "        if obstacleGrid[0][0] == 1:\n",
    "            return []\n",
    "\n",
    "        m = len(obstacleGrid)\n",
    "        n = len(obstacleGrid[0])\n",
    "        if obstacleGrid[m - 1][n - 1] == 1:\n",
    "            return []\n",
    "\n",
    "        \n",
    "        self.ret = None\n",
    "        dirs = [(0, 1), (1, 0)]\n",
    "        def bt(i, j, l, li):\n",
    "            if self.ret is not None:\n",
    "                return\n",
    "            elif i == m - 1 and j == n - 1:\n",
    "                self.ret = l[:li]\n",
    "            else:\n",
    "                for d in dirs:\n",
    "                    nexti = i + d[0]\n",
    "                    nextj = j + d[1]\n",
    "                    if nexti == m or nextj == n or obstacleGrid[nexti][nextj] == 1:\n",
    "                        continue\n",
    "                    \n",
    "                    l[li][0] = nexti\n",
    "                    l[li][1] = nextj\n",
    "                    obstacleGrid[nexti][nextj] = 1\n",
    "                    bt(nexti, nextj, l, li + 1)\n",
    "\n",
    "                    if self.ret:\n",
    "                        return\n",
    "    \n",
    "        l = [ [0, 0] for _ in range(10000) ]\n",
    "        bt(0, 0, l, 1)\n",
    "        return [] if self.ret is None else self.ret\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "        def dfs(i,j):\n",
    "            if not 0<=i<m or not 0<=j<n or obstacleGrid[i][j]==1: return False\n",
    "            if (i,j) in visited:return False\n",
    "            path.append([i,j])\n",
    "            visited.add((i,j))\n",
    "            if i==m-1 and j==n-1:return True           \n",
    "            if dfs(i+1,j) or dfs(i,j+1):return True\n",
    "            path.pop()\n",
    "            return False \n",
    "            \n",
    "        m,n = len(obstacleGrid), len(obstacleGrid[0])\n",
    "        visited = set()\n",
    "        path = []\n",
    "        if obstacleGrid[m-1][n-1]==1:return path\n",
    "        dfs(0,0)\n",
    "        return path"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "        def dfs(i,j):\n",
    "            if not 0<=i<m or not 0<=j<n or obstacleGrid[i][j]==1: return False\n",
    "            if (i,j) in visited:return False\n",
    "            path.append([i,j])\n",
    "            visited.add((i,j))\n",
    "            if i==m-1 and j==n-1:return True           \n",
    "            if dfs(i+1,j) or dfs(i,j+1):return True\n",
    "            path.pop()\n",
    "            return False \n",
    "            \n",
    "        m,n = len(obstacleGrid), len(obstacleGrid[0])\n",
    "        visited = set()\n",
    "        path = []\n",
    "        if obstacleGrid[m-1][n-1]==1:return path\n",
    "        dfs(0,0)\n",
    "        return path"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        def next(point, m, n, obstacleGrid):\n",
    "            x,y = point[0], point[1]\n",
    "            res = []\n",
    "            if x + 1 < m and not obstacleGrid[x + 1][y]: res.append([x + 1, y])\n",
    "            if y + 1 < n and not obstacleGrid[x][y + 1]: res.append([x, y + 1])\n",
    "            return res\n",
    "\n",
    "        if not obstacleGrid:\n",
    "            return []\n",
    "        m, n = len(obstacleGrid), len(obstacleGrid[0])\n",
    "\n",
    "        res = []\n",
    "        path = []\n",
    "        flag = False\n",
    "        visited = {}\n",
    "        def dfs(cur):\n",
    "\n",
    "            nonlocal obstacleGrid, path\n",
    "            nonlocal m,n\n",
    "            nonlocal res, flag, visited\n",
    "            p = (cur[0], cur[1])\n",
    "            if p not in visited:\n",
    "                visited[p] = True\n",
    "            else:\n",
    "                return\n",
    "            if flag:\n",
    "                return\n",
    "            #print(cur)\n",
    "            path.append(cur)\n",
    "            if cur[0] == m - 1 and cur[1] == n - 1 and not obstacleGrid[m - 1][n - 1]:\n",
    "                res = path.copy()\n",
    "                flag = True\n",
    "                return\n",
    "            next_ = next(cur, m, n, obstacleGrid)\n",
    "            for p in next_:\n",
    "                dfs(p)\n",
    "            path.pop()\n",
    "        if obstacleGrid[m - 1][n - 1] or obstacleGrid[0][0]:\n",
    "            return []\n",
    "        dfs([0,0])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "        # 特殊情况判断:  如果起点或终点有障碍物 那么不可能存在可行路径\n",
    "        if obstacleGrid[0][0]==1 or obstacleGrid[-1][-1]==1:\n",
    "            return []\n",
    "        path_all = []\n",
    "        m, n = len(obstacleGrid), len(obstacleGrid[0])\n",
    "        visited=set()\n",
    "        def dfs(r, c, path):\n",
    "            # 如果已经找到一条可行路径 则返回\n",
    "            if len(path_all)>0:\n",
    "                return\n",
    "            # 走到终点 说明找到一条可行路径\n",
    "            if r==m-1 and c==n-1:\n",
    "                path_all.append(path)\n",
    "                return\n",
    "            visited.add((r,c))\n",
    "            # 向下走\n",
    "            if r+1<m and obstacleGrid[r+1][c]==0 and ((r+1, c)  not in visited):\n",
    "                dfs(r+1, c, path+[[r+1,c]])\n",
    "            # 向右走\n",
    "            if c+1<n and obstacleGrid[r][c+1]==0 and ((r, c+1)  not in visited):\n",
    "                dfs(r, c+1, path+[[r,c+1]])\n",
    "        dfs(0,0,[[0,0]])\n",
    "        if len(path_all)>0:\n",
    "            return path_all[0]\n",
    "        else:\n",
    "            return []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "        if obstacleGrid[0][0] == 1:\n",
    "            return []\n",
    "        directions = [(0, 1), (1, 0)]\n",
    "        queue = [((0, 0), [(0, 0)])]\n",
    "        seen = set()\n",
    "        row, col = len(obstacleGrid), len(obstacleGrid[0])\n",
    "\n",
    "        def get_valid_nex_loc(curr_loc, direct):\n",
    "            nex_i = curr_loc[0] + direct[0]\n",
    "            nex_j = curr_loc[1] + direct[1]\n",
    "            if (0 <= nex_i <= row-1) and (0 <= nex_j <= col-1):\n",
    "                return (nex_i, nex_j)\n",
    "        \n",
    "        def is_finish(curr_loc):\n",
    "            if (curr_loc[0] == row-1) and (curr_loc[1] == col-1):\n",
    "                return True\n",
    "\n",
    "        while queue:\n",
    "            curr_loc, curr_path = queue.pop(0)\n",
    "            if is_finish(curr_loc):\n",
    "                return curr_path\n",
    "            for direct in directions:\n",
    "                curr_path_copy = copy.copy(curr_path)\n",
    "                nex_loc = get_valid_nex_loc(curr_loc, direct)\n",
    "                if nex_loc and (nex_loc not in seen) and (obstacleGrid[nex_loc[0]][nex_loc[1]] == 0):\n",
    "                    curr_path_copy.append(nex_loc)\n",
    "                    queue.append(((nex_loc[0], nex_loc[1]), curr_path_copy))\n",
    "                    seen.add(nex_loc)\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef pathWithObstacles(self, obstacleGrid):\n",
    "\t\tself.deadend = set()\n",
    "\t\treturn [] if obstacleGrid[0][0] == 1 else self.dfs(obstacleGrid, 0, 0, [])\n",
    "\t\n",
    "\tdef dfs(self, grid, x, y, stack):\n",
    "\t\tstack.append([x, y])\n",
    "\t\tif x == len(grid) - 1 and y == len(grid[0]) - 1:\n",
    "\t\t\treturn stack\n",
    "\t\tif x + 1 < len(grid) and (x + 1, y) not in self.deadend and grid[x + 1][y] == 0:\n",
    "\t\t\tres = self.dfs(grid, x + 1, y, stack)\n",
    "\t\t\tif res:\n",
    "\t\t\t\treturn stack\n",
    "\t\tif y + 1 < len(grid[0]) and (x, y + 1) not in self.deadend and grid[x][y + 1] == 0:\n",
    "\t\t\tres = self.dfs(grid, x, y + 1, stack)\n",
    "\t\t\tif res:\n",
    "\t\t\t\treturn stack\n",
    "\t\tstack.pop()\n",
    "\t\tself.deadend.add((x, y))\n",
    "\t\treturn []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(obstacleGrid)\n",
    "        if m == 0:\n",
    "            return []\n",
    "        n = len(obstacleGrid[0])\n",
    "        if n == 0:\n",
    "            return []\n",
    "        if obstacleGrid[0][0] == 1:\n",
    "            return []\n",
    "        q, head = [[0, 0]], -1\n",
    "        prev = [[[-1, -1] for _ in range(n)] for __ in range(m)]\n",
    "        visited = [[False] * n for _ in range(m)]\n",
    "        visited[0][0] = True\n",
    "        while head + 1 < len(q):\n",
    "            head += 1\n",
    "            x, y = q[head]\n",
    "            for d in [[0, 1], [1, 0]]:\n",
    "                xx, yy = x + d[0], y + d[1]\n",
    "                if xx < 0 or xx >= m or yy < 0 or yy >= n:\n",
    "                    continue\n",
    "                if visited[xx][yy] or obstacleGrid[xx][yy] == 1:\n",
    "                    continue\n",
    "                q.append([xx, yy])\n",
    "                visited[xx][yy] = True\n",
    "                prev[xx][yy] = [x, y]\n",
    "        if not visited[m - 1][n - 1]:\n",
    "            return []\n",
    "        path = [[m - 1, n - 1]]\n",
    "        while prev[path[-1][0]][path[-1][1]][0] != -1:\n",
    "            path.append(prev[path[-1][0]][path[-1][1]])\n",
    "        return path[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "        @cache\n",
    "        def travel(i, j):\n",
    "            if i >= r or j >= c or obstacleGrid[i][j] == 1 or visited == 1:\n",
    "                return False\n",
    "            path.append([i, j])\n",
    "            visited[i][j] = 1\n",
    "            if i == r - 1 and j == c - 1:\n",
    "                return True\n",
    "            if travel(i, j + 1) or travel(i + 1, j):\n",
    "                return True\n",
    "            path.pop()\n",
    "            return False\n",
    "\n",
    "        if not obstacleGrid or not obstacleGrid[0]:\n",
    "            return []\n",
    "        r, c = len(obstacleGrid), len(obstacleGrid[0])\n",
    "        path, visited = [], [[0] * c for _ in range(r)]\n",
    "        travel(0, 0)\n",
    "        return path\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(obstacleGrid)\n",
    "        n = len(obstacleGrid[0])\n",
    "        if obstacleGrid[-1][-1] == 1 or obstacleGrid[0][0] == 1:\n",
    "            return []\n",
    "        queue = [[[0, 0]]]\n",
    "        visited = set()\n",
    "        visited.add((0, 0))\n",
    "        while queue:\n",
    "            path = queue.pop(0)\n",
    "            # print(path)\n",
    "            situation = path[-1]\n",
    "            if situation == [m-1, n-1]:\n",
    "                return path\n",
    "            # print(situation)\n",
    "            for x, y in [[situation[0]+1, situation[1]], [situation[0], situation[1]+1]]:\n",
    "                # print(x, y)\n",
    "                if 0 <= x < m and 0 <= y < n and obstacleGrid[x][y] == 0 and (x, y) not in visited:\n",
    "                    queue.append(path+[[x, y]])\n",
    "                    visited.add((x, y))\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "        if obstacleGrid[0][0]:\n",
    "            return []\n",
    "        connections = {(0,0):(-1,-1)}\n",
    "        m,n = len(obstacleGrid),len(obstacleGrid[0])\n",
    "        dp = [[False] * n for i in range(m)]\n",
    "        dp[0][0] = True\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if obstacleGrid[i][j]:\n",
    "                    continue\n",
    "                if i > 0 and dp[i-1][j]:\n",
    "                    dp[i][j] = True\n",
    "                    connections[(i,j)] = (i-1,j)\n",
    "                elif j > 0 and dp[i][j-1]:\n",
    "                    dp[i][j] = True\n",
    "                    connections[(i,j)] = (i,j-1)\n",
    "        if not dp[-1][-1]:\n",
    "            return []\n",
    "        result = []\n",
    "        pos = (m-1,n-1)\n",
    "        while pos != (-1,-1):\n",
    "            result.append(pos)\n",
    "            pos = connections[pos]\n",
    "        return result[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def valid(self, p, m, n, visited):\n",
    "        y, x = p\n",
    "        if not (x >= 0 and x < n and y >= 0 and y < m):\n",
    "            return False\n",
    "        if p in visited:\n",
    "            return False\n",
    "        return True\n",
    "\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(obstacleGrid)\n",
    "        n = len(obstacleGrid[0])\n",
    "        if obstacleGrid[0][0] == 1:\n",
    "            return []\n",
    "        q = [[(0, 0), []]]\n",
    "        visited = {q[0][0]}\n",
    "        while len(q) > 0:\n",
    "            position, path_list = q.pop(0)\n",
    "            paths = list(path_list)\n",
    "            paths.append(position)\n",
    "            if position == (m - 1, n - 1):\n",
    "                return paths\n",
    "            y, x = position\n",
    "            p1 = (y, x + 1)\n",
    "            if self.valid(p1, m, n, visited):\n",
    "                visited.add(p1)\n",
    "                if obstacleGrid[p1[0]][p1[1]] == 0:\n",
    "                    q.append([p1, paths])\n",
    "            #\n",
    "            p2 = (y + 1, x)\n",
    "            if self.valid(p2, m, n, visited):\n",
    "                visited.add(p2)\n",
    "                if obstacleGrid[p2[0]][p2[1]] == 0:\n",
    "                    q.append([p2, paths])\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "        if not obstacleGrid:\n",
    "            return []\n",
    "        n, m = len(obstacleGrid), len(obstacleGrid[0])\n",
    "        if obstacleGrid[0][0] or obstacleGrid[n-1][m-1]:\n",
    "            return []\n",
    "        import collections\n",
    "        queue = collections.deque()\n",
    "        queue.append((0, 0, [(0, 0)]))\n",
    "        visited = set([(0, 0)])\n",
    "        path = []\n",
    "        while queue:\n",
    "            x, y, path = queue.popleft()\n",
    "            if x == n-1 and y == m-1:\n",
    "                return path\n",
    "            for dir in [(x+1, y), (x, y+1)]:\n",
    "                if dir[0] >= n or dir[1] >= m:\n",
    "                    continue\n",
    "                if dir in visited or obstacleGrid[dir[0]][dir[1]]:\n",
    "                    continue\n",
    "                path.append((dir[0], dir[1]))\n",
    "                queue.append((dir[0], dir[1], path[::]))\n",
    "                path.pop(-1)\n",
    "                visited.add(dir)\n",
    "        return []\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "        direction = [[0, 1], [1, 0]]\n",
    "        m = len(obstacleGrid)\n",
    "        n = len(obstacleGrid[0])\n",
    "        if m == 1 and n == 1 and obstacleGrid[0][0] == 0:\n",
    "            return [[0, 0]]\n",
    "        if obstacleGrid[0][0] != 0 or obstacleGrid[-1][-1] != 0:\n",
    "            return []\n",
    "        visited = set()\n",
    "        visited.add((0, 0))\n",
    "        queue = []\n",
    "        queue.append([[0, 0]])\n",
    "        while queue:\n",
    "            # print(queue)\n",
    "            cur_path = queue.pop(0)\n",
    "            # print(cur_path)\n",
    "            x, y = cur_path[-1]\n",
    "            # print(x, y)\n",
    "            for dx, dy in direction:\n",
    "                newx = x + dx\n",
    "                newy = y + dy\n",
    "                if 0 <= newx < m and 0 <= newy < n and (newx, newy) not in visited and obstacleGrid[newx][newy] == 0:\n",
    "                    visited.add((newx, newy))\n",
    "                    queue.append(cur_path+[[newx, newy]])\n",
    "                    if newx == m-1 and newy == n-1:\n",
    "                        return cur_path+[[newx, newy]]\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "        ans = list()\n",
    "        if obstacleGrid[0][0] == 1:\n",
    "            return ans\n",
    "        m, n = len(obstacleGrid), len(obstacleGrid[0])\n",
    "        open_set = [((0, 0), [[0, 0]])]\n",
    "        visited = set([(0, 0)])\n",
    "        while open_set:\n",
    "            cur_pos, cur_path = open_set.pop(0)\n",
    "            if cur_pos == (m-1, n-1):\n",
    "                ans = cur_path\n",
    "                break\n",
    "            for move in [(0, 1), (1, 0)]:\n",
    "                next_pos_x, next_pos_y = cur_pos[0] + move[0], cur_pos[1] + move[1]\n",
    "                if next_pos_x < m and next_pos_y < n and obstacleGrid[next_pos_x][next_pos_y] != 1:\n",
    "                    next_pos = (next_pos_x, next_pos_y)\n",
    "                    if next_pos not in visited:\n",
    "                        next_path = cur_path + [[next_pos_x, next_pos_y]]\n",
    "                        open_set.append((next_pos, next_path))\n",
    "                        visited.add(next_pos)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "        m,n=len(obstacleGrid),len(obstacleGrid[0])\n",
    "        if obstacleGrid==[[]] or obstacleGrid[0][0]==1:\n",
    "            return []\n",
    "        dp=[[(0,[-1,-1])]*n for _ in range(m)]\n",
    "        dp[0][0]=(1,[-1,-1])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if j==0:\n",
    "                    if i>0 and obstacleGrid[i][0]==0 and dp[i-1][0][0]>0:\n",
    "                        dp[i][0]=(1,(i-1,0))\n",
    "                elif i==0:\n",
    "                    if j>0 and obstacleGrid[0][j]==0 and dp[0][j-1][0]>0:\n",
    "                        dp[0][j]=(1,(0,j-1))\n",
    "                else:\n",
    "                    if obstacleGrid[i][j]==0:\n",
    "                        if dp[i-1][j][0]>0:\n",
    "                            dp[i][j]=(1,[i-1,j])\n",
    "                        elif dp[i][j-1][0]>0:\n",
    "                            dp[i][j]=(1,[i,j-1])\n",
    "        ans=[]\n",
    "        if dp[-1][-1][0]!=0:\n",
    "            i,j=m-1,n-1\n",
    "            while [i,j]!=[-1,-1]:\n",
    "                ans.append([i,j])\n",
    "                i,j=dp[i][j][1]\n",
    "        return ans[::-1]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "        result = []\n",
    "        @cache\n",
    "        def dfs(x, y):\n",
    "            if x >= len(obstacleGrid) or y >= len(obstacleGrid[0]):\n",
    "                return False\n",
    "            if obstacleGrid[x][y] == 1:\n",
    "                return False\n",
    "            result.append([x, y])\n",
    "            if x == len(obstacleGrid)-1 and y == len(obstacleGrid[0])-1:\n",
    "                return True\n",
    "            if dfs(x+1, y):\n",
    "                return True\n",
    "            if dfs(x, y+1):\n",
    "                return True\n",
    "            result.pop()\n",
    "            return False\n",
    "        dfs(0,0)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "        if obstacleGrid[0][0] != 0 or obstacleGrid[-1][-1] != 0:\n",
    "            return []\n",
    "\n",
    "        m = len(obstacleGrid)\n",
    "        n = len(obstacleGrid[0])\n",
    "        directions = [(0, 1), (1, 0)]\n",
    "        path = []\n",
    "        visited = set()\n",
    "\n",
    "        def dfs(x, y, path):\n",
    "            if x >= m or y >= n or obstacleGrid[x][y] == 1 or (x, y) in visited:\n",
    "                return False\n",
    "\n",
    "            path.append([x, y])\n",
    "            visited.add((x, y))\n",
    "\n",
    "            if x == m - 1 and y == n - 1:\n",
    "                return True\n",
    "\n",
    "            for x_diff, y_diff in directions:\n",
    "                new_x, new_y = x + x_diff, y + y_diff\n",
    "                found = dfs(new_x, new_y, path)\n",
    "                if found:\n",
    "                    return True\n",
    "\n",
    "            path.pop()\n",
    "            return False\n",
    "\n",
    "        dfs(0, 0, path)\n",
    "        return path"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "        #dfs算法\n",
    "      \n",
    "        w,l=len(obstacleGrid),len(obstacleGrid[0])\n",
    "        \n",
    "        def dfs(i,j,path):\n",
    "            if res:return\n",
    "            if obstacleGrid[i][j]==1:return\n",
    "            if i==w-1 and j==l-1:\n",
    "                res.append(path)\n",
    "            isVis.add((i,j))\n",
    "            if j+1<l and obstacleGrid[i][j+1]==0 and (i,j+1) not in isVis:\n",
    "                dfs(i,j+1,path+[[i,j+1]])\n",
    "            if i+1<w and obstacleGrid[i+1][j]==0 and (i+1,j) not in isVis:\n",
    "                dfs(i+1,j,path+[[i+1,j]])\n",
    "            \n",
    "        res=[]\n",
    "        isVis=set()\n",
    "        dfs(0,0,[[0,0]])\n",
    "        return res[0] if res else []\n",
    "\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "        \"\"\"\n",
    "        def do(maze, r, c, is_arrival, path_list):\n",
    "\n",
    "            if r == len(maze) or c == len(maze[0]):\n",
    "                return False\n",
    "            if is_arrival[r][c] is True:\n",
    "                return \n",
    "            if r == len(maze)-1 and c == len(maze[0])-1 and maze[r][c] == 0:\n",
    "                path_list.append([r, c])\n",
    "                return True\n",
    "\n",
    "            o = maze[r][c]\n",
    "\n",
    "            if o == 0:\n",
    "                path_list.append([r, c])\n",
    "                \n",
    "            else:\n",
    "                return False\n",
    "            # print(is_arrival, r, c)\n",
    "            is_arrival[r][c] = True \n",
    "            r_ret = do(maze, r+1, c, is_arrival, path_list)\n",
    "            if r_ret:\n",
    "                return True\n",
    "            c_ret = do(maze, r, c+1, is_arrival, path_list)\n",
    "            # print(path_list)\n",
    "            if c_ret:\n",
    "                return True\n",
    "            \n",
    "            path_list.pop(-1)\n",
    "            \n",
    "            return False\n",
    "\n",
    "        if obstacleGrid == [[0]]:\n",
    "            return [[0,0]]\n",
    "        if obstacleGrid[0][0] == 1:\n",
    "            return []\n",
    "\n",
    "        path_list = []\n",
    "        # 注意不能用\"[False]*len()\"来初始化矩阵\n",
    "        is_arrival = [[False for n in range(len(obstacleGrid[0]))] for m in range(len(obstacleGrid))]\n",
    "        ret = do(obstacleGrid, 0, 0, is_arrival, path_list)\n",
    "        print(ret)\n",
    "        if ret:\n",
    "            return path_list\n",
    "\n",
    "        return []\n",
    "        \"\"\"\n",
    "\n",
    "        import copy\n",
    "\n",
    "        rLength = len(obstacleGrid)\n",
    "        cLength = len(obstacleGrid[0])\n",
    "\n",
    "        finalPath = []\n",
    "        #path = []\n",
    "        visited = set()\n",
    "        def fn(maze, r, c, path):\n",
    "\n",
    "            if r >= rLength or c >= cLength or (r,c) in visited or maze[r][c]==1:\n",
    "               return\n",
    "\n",
    "            if r == rLength-1 and c == cLength-1 and maze[r][c] == 0:\n",
    "                path.append((r, c))\n",
    "                finalPath.append(path.copy())\n",
    "                #print(finalPath)\n",
    "                return \n",
    "            \n",
    "            curr = maze[r][c]\n",
    "\n",
    "            visited.add((r,c))\n",
    "\n",
    "            path.append((r, c))\n",
    "\n",
    "            fn(maze, r+1, c,   path)\n",
    "            fn(maze, r,   c+1, path)\n",
    "\n",
    "            path.pop()\n",
    "\n",
    "        \n",
    "        fn(obstacleGrid, 0, 0, [])\n",
    "\n",
    "        if finalPath != []:\n",
    "            return finalPath[0]\n",
    "        else:\n",
    "            return []\n",
    "            \n",
    "            \n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:      \n",
    "\n",
    "        m, n = len(obstacleGrid), len(obstacleGrid[0])\n",
    "        # if obstacleGrid[m-1][n-1]==1 or obstacleGrid[0][0]==1:\n",
    "        #     return []\n",
    "\n",
    "        self.res = []\n",
    "\n",
    "        @cache\n",
    "        def dfs(x, y):\n",
    "            if x==m-1 and y==n-1:\n",
    "                return True\n",
    "            \n",
    "\n",
    "            for tx, ty in [(x+1, y), (x, y+1)]:\n",
    "                if 0<=tx<m and 0<=ty<n and obstacleGrid[tx][ty]!=1:\n",
    "                    self.res.append([tx, ty])\n",
    "                    # 如果找到一条路径，一路返回！\n",
    "                    if dfs(tx, ty):\n",
    "                        return True\n",
    "                    self.res.pop()\n",
    "        \n",
    "        \n",
    "        if obstacleGrid[0][0] != 1:\n",
    "            self.res.append([0,0])\n",
    "        else:\n",
    "            return []\n",
    "        \n",
    "        \n",
    "        if dfs(0, 0):\n",
    "            return self.res\n",
    "        else:\n",
    "            return []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "        visited = set()\n",
    "        visited.add((0, 0))\n",
    "        m, n = len(obstacleGrid), len(obstacleGrid[0])\n",
    "        if obstacleGrid[-1][-1] == 1 or obstacleGrid[0][0] == 1:\n",
    "            return []\n",
    "        def dfs(x, y):\n",
    "            if x == m-1 and y == n-1:\n",
    "                return [[x, y]]\n",
    "            \n",
    "            for i, j in [[0,1], [1,0]]:\n",
    "                nx, ny = x+i, y+j\n",
    "                if nx < m and ny < n and (nx, ny) not in visited and obstacleGrid[nx][ny] != 1:\n",
    "                    visited.add((nx, ny))\n",
    "                    res = dfs(nx, ny)\n",
    "                    if res:\n",
    "                        \n",
    "                        return [[x, y]]+res\n",
    "            return []\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        res = []\n",
    "        temp = []\n",
    "        record = set()\n",
    "        row = len(obstacleGrid)\n",
    "        col = len(obstacleGrid[0])\n",
    "        def backtrack(i,j):\n",
    "            if i == row or j==col or obstacleGrid[i][j]==1 or len(res)>0 or (i,j) in record:\n",
    "                return\n",
    "            temp.append([i,j])\n",
    "            record.add((i,j))\n",
    "            if i == row-1  and j == col-1 and obstacleGrid[i][j]==0:\n",
    "                res.append(temp[:])\n",
    "                temp.pop()\n",
    "                return\n",
    "            backtrack(i+1,j)\n",
    "            backtrack(i,j+1)\n",
    "            temp.pop()\n",
    "        backtrack(0,0)\n",
    "        return res[0] if len(res)>0 else []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:      \n",
    "\n",
    "        m, n = len(obstacleGrid), len(obstacleGrid[0])\n",
    "        # if obstacleGrid[m-1][n-1]==1 or obstacleGrid[0][0]==1:\n",
    "        #     return []\n",
    "\n",
    "        self.res = []\n",
    "\n",
    "        @cache\n",
    "        def dfs(x, y):\n",
    "            if x==m-1 and y==n-1:\n",
    "                return True\n",
    "            \n",
    "\n",
    "            for tx, ty in [(x+1, y), (x, y+1)]:\n",
    "                if 0<=tx<m and 0<=ty<n and obstacleGrid[tx][ty]!=1:\n",
    "                    self.res.append([tx, ty])\n",
    "                    # 如果找到一条路径，一路返回！\n",
    "                    if dfs(tx, ty):\n",
    "                        return True\n",
    "                    self.res.pop()\n",
    "        \n",
    "        \n",
    "        if obstacleGrid[0][0] != 1:\n",
    "            self.res.append([0,0])\n",
    "        else:\n",
    "            return []\n",
    "        \n",
    "        \n",
    "        if dfs(0, 0):\n",
    "            return self.res\n",
    "        else:\n",
    "            return []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "        path = []\n",
    "        diec = [(0,1),(1,0)]\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if i == len(obstacleGrid)-1 and j == len(obstacleGrid[0])-1:\n",
    "                if obstacleGrid[i][j] != 1:\n",
    "                    path.append([i,j])\n",
    "                    return True\n",
    "                else:\n",
    "                    return False\n",
    "            if 0 <= i < len(obstacleGrid) and 0 <= j < len(obstacleGrid[0]) and obstacleGrid[i][j] != 1:\n",
    "                obstacleGrid[i][j] = 1\n",
    "                path.append([i,j])\n",
    "                for m,n in diec:\n",
    "                    if dfs(i+m,j+n):\n",
    "                        return True\n",
    "                obstacleGrid[i][j] = 0\n",
    "                path.pop()\n",
    "                return False\n",
    "        dfs(0,0)\n",
    "        return path\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "        result = []\n",
    "        res = []\n",
    "        r = 0\n",
    "        c = 0\n",
    "        if not obstacleGrid:\n",
    "            return []\n",
    "        r_n = len(obstacleGrid)\n",
    "        c_n = len(obstacleGrid[0])\n",
    "        got = False\n",
    "        visited=set()\n",
    "\n",
    "        def backtrack(r, c, obstacleGrid):\n",
    "            nonlocal got\n",
    "            if got:\n",
    "                return\n",
    "            # 遇到障碍\n",
    "            if r >= r_n or c >= c_n:\n",
    "                return\n",
    "            if obstacleGrid[r][c] == 1:\n",
    "                return\n",
    "            result.append([r, c])\n",
    "            visited.add((r, c))\n",
    "            if r == r_n-1 and c == c_n-1:\n",
    "                res.append(result[:])\n",
    "                got = True\n",
    "            if ((r+1, c) not in visited):\n",
    "                backtrack(r+1, c, obstacleGrid)\n",
    "            if ((r, c+1) not in visited):\n",
    "                backtrack(r, c+1, obstacleGrid)\n",
    "            result.pop()\n",
    "        backtrack(r, c, obstacleGrid)\n",
    "        if not res:\n",
    "            return []\n",
    "        else:\n",
    "            return res[0]\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "        path = []\n",
    "        seen = set()\n",
    "        def backtrack(i, j):\n",
    "            if (i,j) in seen or not 0<=i<len(obstacleGrid) or not 0<=j<len(obstacleGrid[0]) or obstacleGrid[i][j] == 1:\n",
    "                return False\n",
    "            seen.add((i,j))\n",
    "            path.append([i,j])\n",
    "            if (i, j) == (len(obstacleGrid)-1, len(obstacleGrid[0])-1) or backtrack(i+1, j) or backtrack(i, j+1):\n",
    "                return True\n",
    "            path.pop()\n",
    "        backtrack(0, 0)\n",
    "        return path\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "        path = []\n",
    "        diec = [(0,1),(1,0)]\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if i == len(obstacleGrid)-1 and j == len(obstacleGrid[0])-1:\n",
    "                if obstacleGrid[i][j] != 1:\n",
    "                    path.append([i,j])\n",
    "                    return True\n",
    "                else:\n",
    "                    return False\n",
    "            if 0 <= i < len(obstacleGrid) and 0 <= j < len(obstacleGrid[0]) and obstacleGrid[i][j] != 1:\n",
    "                obstacleGrid[i][j] = 1\n",
    "                path.append([i,j])\n",
    "                for m,n in diec:\n",
    "                    if dfs(i+m,j+n):\n",
    "                        return True\n",
    "                obstacleGrid[i][j] = 0\n",
    "                path.pop()\n",
    "                return False\n",
    "        dfs(0,0)\n",
    "        return path\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "        m,n = len(obstacleGrid),len(obstacleGrid[0])\n",
    "        path = []\n",
    "        seen = set()\n",
    "        def dfs(i,j):\n",
    "            if (i,j) in seen or not 0 <= i < m or not 0 <= j < n or obstacleGrid[i][j] == 1:\n",
    "                return False\n",
    "            seen.add((i,j))\n",
    "            path.append([i,j])\n",
    "            if (i,j) == (m-1,n-1) or dfs(i+1,j) or dfs(i,j+1):\n",
    "                return True\n",
    "            path.pop()\n",
    "        \n",
    "        dfs(0,0)\n",
    "        return path\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "        path = [[0,0]]\n",
    "        data = []\n",
    "        m,n = len(obstacleGrid),len(obstacleGrid[0])\n",
    "        @cache\n",
    "        def dfs(r,c):\n",
    "            nonlocal data\n",
    "            if data:\n",
    "                return\n",
    "            if obstacleGrid[r][c]:\n",
    "                #print(f'非法坐标{r,c}')\n",
    "                return \n",
    "            if (r,c) == (m-1,n-1):\n",
    "                #print(f'到达终点{path}')\n",
    "                data = path[:]\n",
    "                return\n",
    "            for x,y in ((0,1),(1,0)):\n",
    "                new_r,new_c = r+x,c+y\n",
    "                if 0 <= new_r < m and 0 <= new_c < n:\n",
    "                    path.append([r+x,c+y])\n",
    "                    dfs(r+x,c+y)\n",
    "                    path.pop()\n",
    "        dfs(0,0)\n",
    "        return data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(obstacleGrid), len(obstacleGrid[0])\n",
    "        Can_Visit = [[True]*n for _ in range(m)]\n",
    "        path = {}\n",
    "\n",
    "        def dfs(x, y):\n",
    "            nonlocal m, n\n",
    "            if x == m-1 and y == n-1 and obstacleGrid[x][y]!=1: return [[x, y]]\n",
    "            if (x, y) in path:\n",
    "                return path[(x, y)]\n",
    "            if 0 <= x < m and 0 <= y < n and obstacleGrid[x][y]!=1 and Can_Visit[x][y]:\n",
    "                Can_Visit[x][y] = False\n",
    "                for d in [[0, 1], [1, 0]]:\n",
    "                    tmp_path = dfs(d[0]+x, d[1]+y)\n",
    "                    path[(d[0]+x, d[1]+y)]= tmp_path\n",
    "                    if tmp_path: \n",
    "                        return [[x, y]] + tmp_path\n",
    "                Can_Visit[x][y] = True\n",
    "            path[(x, y)] = []\n",
    "            return []\n",
    "\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "        directions=[[1,0],[0,1]]\n",
    "        m=len(obstacleGrid)\n",
    "        n=len(obstacleGrid[0])\n",
    "        if m==1 and n==1 and obstacleGrid[0][0]==0:\n",
    "            return [[0,0]]\n",
    "        visited=[[False]*n for i in range(m)]\n",
    "        flag=[False]\n",
    "        edges={}\n",
    "        def dfs(x,y):\n",
    "            visited[x][y]=True\n",
    "            for direction in directions:\n",
    "                if x+direction[0]>=0 and x+direction[0]<m and y+direction[1]>=0 and y+direction[1]<n:\n",
    "                    if obstacleGrid[x+direction[0]][y+direction[1]]==0 and visited[x+direction[0]][y+direction[1]]==False:\n",
    "                        edges[(x+direction[0],y+direction[1])]=(x,y)\n",
    "                        if x+direction[0]==m-1 and y+direction[1]==n-1:\n",
    "                            flag[0]=True\n",
    "                        dfs(x+direction[0],y+direction[1])\n",
    "        if obstacleGrid[0][0]==0:\n",
    "            dfs(0,0)\n",
    "        else:\n",
    "            return []\n",
    "        if flag[0]:\n",
    "            ans=[]\n",
    "            p=(m-1,n-1)\n",
    "            while p!=(0,0):\n",
    "                ans.append(list(p))\n",
    "                p=edges[p]\n",
    "\n",
    "            ans.append([0,0])\n",
    "            return ans[::-1]\n",
    "        else:\n",
    "            return []\n",
    "                            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(obstacleGrid), len(obstacleGrid[0])\n",
    "\n",
    "        @cache\n",
    "        def bt(x, y):\n",
    "            if x == m - 1 and y == n - 1:\n",
    "                return path\n",
    "            for nx, ny in ((x, y + 1), (x + 1, y)):\n",
    "                if 0 <= nx < m and 0 <= ny < n and not obstacleGrid[nx][ny]:\n",
    "                    path.append([nx, ny])\n",
    "                    if l := bt(nx, ny): return l\n",
    "                    path.pop()\n",
    "            return []\n",
    "\n",
    "        path = [[0, 0]]\n",
    "        return [] if obstacleGrid[0][0] else bt(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(obstacleGrid), len(obstacleGrid[0])\n",
    "\n",
    "        @cache\n",
    "        def bt(x, y):\n",
    "            if x == m - 1 and y == n - 1:\n",
    "                return path\n",
    "            for nx, ny in ((x, y + 1), (x + 1, y)):\n",
    "                if 0 <= nx < m and 0 <= ny < n and not obstacleGrid[nx][ny]:\n",
    "                    path.append([nx, ny])\n",
    "                    if l := bt(nx, ny): return l\n",
    "                    path.pop()\n",
    "            return []\n",
    "\n",
    "        path = [[0, 0]]\n",
    "        return [] if obstacleGrid[0][0] else bt(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "        # directions=[[1,0],[0,1]]\n",
    "        # m=len(obstacleGrid)\n",
    "        # n=len(obstacleGrid[0])\n",
    "        # if m==1 and n==1 and obstacleGrid[0][0]==0:\n",
    "        #     return [[0,0]]\n",
    "        # visited=[[False]*n for i in range(m)]\n",
    "        # flag=[False]\n",
    "        # edges={}\n",
    "        # def dfs(x,y):\n",
    "        #     visited[x][y]=True\n",
    "        #     for direction in directions:\n",
    "        #         if x+direction[0]>=0 and x+direction[0]<m and y+direction[1]>=0 and y+direction[1]<n:\n",
    "        #             if obstacleGrid[x+direction[0]][y+direction[1]]==0 and visited[x+direction[0]][y+direction[1]]==False:\n",
    "        #                 edges[(x+direction[0],y+direction[1])]=(x,y)\n",
    "        #                 if x+direction[0]==m-1 and y+direction[1]==n-1:\n",
    "        #                     flag[0]=True\n",
    "        #                 dfs(x+direction[0],y+direction[1])\n",
    "        # if obstacleGrid[0][0]==0:\n",
    "        #     dfs(0,0)\n",
    "        # else:\n",
    "        #     return []\n",
    "        # if flag[0]:\n",
    "        #     ans=[]\n",
    "        #     p=(m-1,n-1)\n",
    "        #     while p!=(0,0):\n",
    "        #         ans.append(list(p))\n",
    "        #         p=edges[p]\n",
    "\n",
    "        #     ans.append([0,0])\n",
    "        #     return ans[::-1]\n",
    "        # else:\n",
    "        #     return []\n",
    "\n",
    "\n",
    "\n",
    "        directions=[[1,0],[0,1]]\n",
    "        m=len(obstacleGrid)\n",
    "        n=len(obstacleGrid[0])\n",
    "        if m==1 and n==1 and obstacleGrid[0][0]==0:\n",
    "            return [[0,0]]\n",
    "        visited=[[False]*n for i in range(m)]\n",
    "        flag=[False]\n",
    "        edges={}\n",
    "        path=[]\n",
    "        ans=[]\n",
    "        def dfs(x,y):\n",
    "            visited[x][y]=True\n",
    "            path.append([x,y])\n",
    "            for direction in directions:\n",
    "                if x+direction[0]>=0 and x+direction[0]<m and y+direction[1]>=0 and y+direction[1]<n:\n",
    "                    if obstacleGrid[x+direction[0]][y+direction[1]]==0 and visited[x+direction[0]][y+direction[1]]==False:\n",
    "                        edges[(x+direction[0],y+direction[1])]=(x,y)\n",
    "                        if x+direction[0]==m-1 and y+direction[1]==n-1:\n",
    "                            flag[0]=True\n",
    "                            p=path[:]\n",
    "                            p.append([x+direction[0],y+direction[1]])\n",
    "                            ans.append(p)\n",
    "                        dfs(x+direction[0],y+direction[1])\n",
    "            path.pop()\n",
    "        if obstacleGrid[0][0]==0:\n",
    "            dfs(0,0)\n",
    "        else:\n",
    "            return []\n",
    "        if flag[0]:\n",
    "            return ans[0]\n",
    "        else:\n",
    "            return []\n",
    "\n",
    "\n",
    "\n",
    "                            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(obstacleGrid), len(obstacleGrid[0])\n",
    "        dp = [[None]*n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i==0 and j==0:\n",
    "                    if obstacleGrid[i][j]==0:\n",
    "                        dp[i][j] = 'start'\n",
    "                elif i==0:\n",
    "                    if obstacleGrid[i][j]==1 or dp[i][j-1] is None:\n",
    "                        continue\n",
    "                    dp[i][j] = [(i, j-1)]\n",
    "                elif j==0:\n",
    "                    if obstacleGrid[i][j]==1 or dp[i-1][j] is None:\n",
    "                        continue\n",
    "                    dp[i][j] = [(i-1, j)]\n",
    "                else:\n",
    "                    if obstacleGrid[i][j]==1 or (dp[i-1][j] is None and dp[i][j-1] is None):\n",
    "                        continue\n",
    "                    entry = []\n",
    "                    if dp[i-1][j]:\n",
    "                        entry.append((i-1, j))\n",
    "                    if dp[i][j-1]:\n",
    "                        entry.append((i, j-1))\n",
    "                    dp[i][j] = entry\n",
    "        results = []\n",
    "        i, j = m-1, n-1\n",
    "        while(True):\n",
    "            if dp[i][j] is None:\n",
    "                break\n",
    "            results.insert(0, [i,j])\n",
    "            if dp[i][j]=='start':\n",
    "                break\n",
    "            i, j = dp[i][j][0]\n",
    "        return results\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.i = 0\n",
    "        self.j = 0\n",
    "        self.matrix = [[]]\n",
    "        self.b = True\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "        if self.b == True:\n",
    "            self.matrix = [[0]*len(obstacleGrid[0]) for _ in range(len(obstacleGrid))]\n",
    "        if not obstacleGrid[0] or obstacleGrid[0][0]==1:\n",
    "            return []\n",
    "        if self.b == True:\n",
    "            self.matrix = [[0]*len(obstacleGrid[0]) for _ in range(len(obstacleGrid))]\n",
    "            self.b = False\n",
    "        if self.matrix[self.i][self.j] == 1:\n",
    "            return []\n",
    "        self.matrix[self.i][self.j] = 1\n",
    "        \n",
    "        res = []\n",
    "        \n",
    "        if len(obstacleGrid)==1 and len(obstacleGrid[0])==1:\n",
    "            return [[0,0]]\n",
    "        \n",
    "        if len(obstacleGrid) > 1:\n",
    "            self.i += 1\n",
    "            a = self.pathWithObstacles(obstacleGrid[1:])\n",
    "            if a:\n",
    "                res = [[0,0]]\n",
    "                res += [[x[0]+1,x[1]] for x in a]\n",
    "\n",
    "                return res\n",
    "            self.i -= 1\n",
    "        self.j += 1\n",
    "        a = self.pathWithObstacles([x[1:] for x in obstacleGrid])\n",
    "        if a:\n",
    "            res = [[0,0]]\n",
    "            res += [[x[0],x[1]+1] for x in a]\n",
    "\n",
    "            return res\n",
    "        self.j -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.i = 0\n",
    "        self.j = 0\n",
    "        self.matrix = [[]]\n",
    "        self.b = True\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "        \n",
    "        if self.b == True:\n",
    "            self.matrix = [[0]*len(obstacleGrid[0]) for _ in range(len(obstacleGrid))]\n",
    "            self.b = False\n",
    "        \n",
    "        # if not obstacleGrid[0] or obstacleGrid[0][0]==1:\n",
    "        #     return []            \n",
    "        # if self.matrix[self.i][self.j] == 1:\n",
    "        #     return []\n",
    "        try:\n",
    "            self.matrix[self.i][self.j] = 1\n",
    "        except IndexError:\n",
    "            return []\n",
    "        if obstacleGrid[0][0]==1:\n",
    "            return []\n",
    "        \n",
    "        \n",
    "        if len(obstacleGrid)==1 and len(obstacleGrid[0])==1:\n",
    "            return [[self.i,self.j]]\n",
    "        \n",
    "        if len(obstacleGrid) > 1 and self.matrix[self.i+1][self.j] == 0:\n",
    "            self.i += 1\n",
    "            a = self.pathWithObstacles(obstacleGrid[1:])\n",
    "            if a:\n",
    "                self.i -= 1\n",
    "                res = [[self.i,self.j]]\n",
    "                res += a\n",
    "                return res\n",
    "            else:\n",
    "                self.i -= 1\n",
    "        \n",
    "        if len(obstacleGrid[0]) > 1 and self.matrix[self.i][self.j+1] == 0:\n",
    "            self.j += 1\n",
    "            a = self.pathWithObstacles([x[1:] for x in obstacleGrid])        \n",
    "            if a:\n",
    "                self.j -= 1\n",
    "                res = [[self.i,self.j]]\n",
    "                res += a\n",
    "                return res\n",
    "            else:\n",
    "                self.j -= 1\n",
    "        \n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "        \n",
    "        def dfs(x: int, y: int, path: List[List[int]]) -> bool:\n",
    "            if obstacleGrid[x][y] == 1:\n",
    "                return False\n",
    "\n",
    "            path.append([x, y])\n",
    "            visited.add((x, y))\n",
    "            if x == m - 1 and y == n - 1:\n",
    "                nonlocal ans\n",
    "                ans = path.copy()\n",
    "                return True\n",
    "\n",
    "            for i, j in directions:\n",
    "                _x, _y = x + i, y + j\n",
    "\n",
    "                if 0 <= _x < m and 0 <= _y < n and (_x, _y) not in visited:\n",
    "                    if dfs(_x, _y, path):\n",
    "                        return True\n",
    "                    \n",
    "            path.pop()\n",
    "            return False\n",
    "\n",
    "        m, n = len(obstacleGrid), len(obstacleGrid[0])\n",
    "        directions = [(0, 1), (1, 0)]\n",
    "        path = []\n",
    "        ans = []\n",
    "        visited = set()\n",
    "        dfs(0, 0, path)\n",
    "\n",
    "        return ans\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "        if obstacleGrid[0][0] == 1:\n",
    "            return []\n",
    "\n",
    "        row = len(obstacleGrid)\n",
    "        col = len(obstacleGrid[0])\n",
    "        def dfs(x, y):\n",
    "            nonlocal res\n",
    "            if x == row-1 and y == col-1 and obstacleGrid[x][y] == 0:\n",
    "                res.append(path[:])\n",
    "                return\n",
    "\n",
    "            for nx, ny in [(x+1, y), (x, y+1)]:\n",
    "                if nx < row and ny < col and obstacleGrid[nx][ny] == 0 and (nx, ny) not in visited:\n",
    "                    path.append([nx, ny])\n",
    "                    visited.add((nx, ny))\n",
    "                    dfs(nx, ny)\n",
    "                    path.pop()\n",
    "\n",
    "                \n",
    "        path = [[0,0]]\n",
    "        res = []\n",
    "        visited = {(0,0)}\n",
    "        dfs(0, 0)\n",
    "        return res[0] if res else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:\n",
    "        m,n=len(obstacleGrid), len(obstacleGrid[0])\n",
    "        path=[]\n",
    "        ans=[]\n",
    "        visited=set()\n",
    "        def dfs(x,y,path):\n",
    "            nonlocal ans\n",
    "            nonlocal visited\n",
    "            visited.add((x,y))\n",
    "            if obstacleGrid[x][y]==1:\n",
    "                return\n",
    "            if x==m-1 and y==n-1:\n",
    "                path.append([x,y])\n",
    "                ans=path.copy()\n",
    "                return\n",
    "            if x==m or y==n:\n",
    "                return\n",
    "            if x+1<m and (x+1,y) not in visited:\n",
    "                dfs(x+1,y,path+[[x,y]])\n",
    "            if y+1<n and (x,y+1) not in visited:\n",
    "                dfs(x,y+1,path+[[x,y]])\n",
    "        dfs(0,0,[])\n",
    "        return ans\n",
    "        # if obstacleGrid[0][0]:\n",
    "        #     return []\n",
    "        # dp=[[0]*n for _ in range(m)]\n",
    "        # for "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
